CF208E Blood Cousins

和 $u$ 拥有共同的 $k$ 级祖先的点数就是 $u$ 的 $k$ 级祖先的 $k$ 级儿子的数量 $-1$.

再转换一下就是以 $u$ 的 $k$ 级祖先为根的子树内深度为 $dep_u+k$ 的点的个数$-1$。

然后用 $cnt_d$ 表示深度为 $d$ 的点数，直接 $\text{dsu~on~tree}$ 即可。

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;

const int MAXN = 1e5 , MAXK = 20;
int n , m , col[ MAXN + 5 ];
struct Query{ int id , dep; };
vector< Query > Qry[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];

int dep[ MAXN + 5 ] , Size[ MAXN + 5 ] , Son[ MAXN + 5 ];
int Anc[ MAXN + 5 ][ MAXK + 5 ];
void dfs1( int u , int fa ) {
	dep[ u ] = dep[ fa ] + 1 , Size[ u ] = 1;
	Anc[ u ][ 0 ] = fa;
	for( int i = 1 ; i <= MAXK ; i ++ ) Anc[ u ][ i ] = Anc[ Anc[ u ][ i - 1 ] ][ i - 1 ];
	for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( v == fa ) continue;
		dfs1( v , u ); Size[ u ] += Size[ v ];
		if( Size[ Son[ u ] ] < Size[ v ] ) Son[ u ] = v;
	}
}

int Cnt[ MAXN + 5 ];
int Ans[ MAXN + 5 ] , Sonu;
void Count( int u , int fa , int val ) {
	Cnt[ dep[ u ] ] += val;
	
	for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( v == fa || v == Sonu ) continue;
		Count( v , u , val );
	} 
}
bool vis[ MAXN + 5 ];
void dfs2( int u , int fa , bool is_hs ) {
	vis[ u ] = 1;
	for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( v == fa || v == Son[ u ] ) continue;
		dfs2( v , u , 0 );
	}
	if( Son[ u ] ) dfs2( Son[ u ] , u , 1 );
	Sonu = Son[ u ]; Count( u , fa , 1 ); Sonu = 0;
	for( int i = 0 ; i < Qry[ u ].size() ; i ++ ) Ans[ Qry[ u ][ i ].id ] = Cnt[ dep[ u ] + Qry[ u ][ i ].dep ] - 1;
	if( !is_hs ) Count( u , fa , -1 );
}

int main( ) {
	scanf("%d",&n);
	for( int i = 1 , fa ; i <= n ; i ++ ) {
		scanf("%d",&fa);
		Graph[ fa ].push_back( i );
	}
	
	for( int i = 1 ; i <= n ; i ++ )
		if( !dep[ i ] ) dfs1( i , 0 );
	
	scanf("%d",&m);
	for( int i = 1 , rt , k ; i <= m ; i ++ ) {
		scanf("%d %d",&rt,&k);
		for( int i = 0 ; i <= MAXK ; i ++ ) if( ( k >> i ) & 1 ) rt = Anc[ rt ][ i ];
		Qry[ rt ].push_back( { i , k } );
	}
	
	for( int i = 1 ; i <= n ; i ++ )
		if( !vis[ i ] ) dfs2( i , 0 , 0 );
	
	for( int i = 1 ; i <= m ; i ++ )
		printf("%d ", Ans[ i ] );
	return 0;
} 

再说说这道题的加强版 P5384 [Cnoi2019]雪松果树。

出题人卡了空间，正常写法只有 40 pts。

首先倍增数组太占空间，考虑离线求出 $k$ 级祖先。

$\text{dfs}$ 时可以用栈维护根到当前节点的路径上的点。

那么它的 $k$ 级祖先就应该是栈中的第 $k+1$ 个元素。

然后你就多得了 4 pts 了。

将 $\text{vector}$ 改成链表，再卡卡常就可以过了。

虽然正解是长链剖分